package 力扣._287_寻找重复数;

import java.util.*;

public class Solution {
    public int findDuplicate(int[] nums) {
        //先用hash写个
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num))
                return num;
            set.add(num);
        }
        return 0;
    }

    public int findDuplicate2(int[] nums) {
        if (nums.length < 2)
            return -1;
        //快慢指针，重复值看作是指向同一节点,则一定存在环
        int slow = 0, fast = 0;
        do {      //找到相遇点
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        //找到环入口
        int p = 0;
        while (p != slow) {
            p = nums[p];
            slow = nums[slow];
        }
        return slow;
    }
}
